package string_question.leecode.test5;

/**
 * 最长回文子串
 *
 * @author code_yc
 * @version 1.0
 * @date 2020/7/5 11:53
 */
public class Solution1 {

    // 解法一： 动态规划
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                if (len == 1) {
                    dp[i][j] = true;
                } else {
                    if (s.charAt(i) == s.charAt(j)) {
                        if (j - i < 3 || dp[i + 1][j - 1]) {
                            dp[i][j] = true;
                            if (len > maxLen) {
                                start = i;
                                maxLen = len;
                            }
                        }
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}
